/// @tags: NetFlow CostFlow
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>

int const N = 1e3 + 5, INF = 0x3f3f3f3f;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

struct Edge {
  int v, nxt, f, c;
} e[N << 3];

int n, k, e_cnt = 1, s, t, cost;
int heads[N], l[N], r[N], hash[N * 2], dis[N], cur[N];
bool vis[N];
std::queue<int> q;

inline void add(int u, int v, int f, int c) {
  fprintf(stderr, "%d %d %d\n", u, v, c);
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].f = f,
  e[e_cnt].c = c;
  e[++e_cnt].v = u, e[e_cnt].nxt = heads[v], heads[v] = e_cnt, e[e_cnt].f = 0,
  e[e_cnt].c = -c;
}

inline bool spfa() {
  static bool vis[N];
  while (!q.empty()) q.pop();
  memset(vis, 0, sizeof(vis));
  memset(dis, -0x3f, sizeof(dis));
  memcpy(cur, heads, sizeof(cur));
  q.push(s);
  dis[s] = 0, vis[s] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = false;
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (dis[v = e[i].v] < dis[u] + e[i].c && e[i].f) {
        dis[v] = dis[u] + e[i].c;
        if (v == t) return true;
        if (!vis[v]) q.push(v), vis[v] = true;
      }
    }
  }
  return false;
}

int dinic(int u, int flow) {
  if (u == t) return flow;
  int rest = flow, k;
  vis[u] = true;
  for (int i = heads[u], v; i && rest; i = e[i].nxt) {
    if (dis[v = e[i].v] == dis[u] + e[i].c && !vis[v] && e[i].f) {
      k = dinic(v, std::min(rest, e[i].f));
      if (k) {
        cost += k * e[i].c;
        e[i].f -= k;
        e[i ^ 1].f += k;
        rest -= k;
      }
    }
  }
  return flow - rest;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3358 最长k可重区间集问题.in", "r", stdin);
  freopen("P3358 最长k可重区间集问题.out", "w", stdout);
#endif
#endif

  read(n), read(k);
  for (int i = 1; i <= n; ++i) {
    hash[++*hash] = read(l[i]);
    hash[++*hash] = read(r[i]);
  }
  std::sort(hash + 1, hash + *hash + 1);
  *hash = std::unique(hash + 1, hash + *hash + 1) - hash - 1;
  s = 0, t = *hash + 1;
  for (int i = 1; i <= n; ++i) {
    l[i] = std::lower_bound(hash + 1, hash + *hash + 1, l[i]) - hash;
    r[i] = std::lower_bound(hash + 1, hash + *hash + 1, r[i]) - hash;
  }
  for (int i = 0; i <= *hash; ++i) add(i, i + 1, k, 0);
  for (int i = 1; i <= n; ++i) add(l[i], r[i], 1, hash[r[i]] - hash[l[i]]);
  while (spfa()) { dinic(s, k); }
  printf("%d", cost);
  return 0;
}